\section{%% Algorithm Framework for 
Path-Tree Cover For Reachability Query}
\label{pathtree}

In this paper, we propose to use a novel graph structure, {\em
  Path-Tree}, to cover a DAG $G$.  The path-tree cover is a spanning
subgraph of $G$ in a tree shape.
%%  which is described by tree
%% $T=(V_T,E_T)$: Each vertex $v$ of $G$ is uniquely mapped to a single
%% vertex in $T$, denoted as $f(v) \in V_T$ and each edge $(u,v)$ in
%% $E^\prime$ is uniquely mapped to a single edge in $T$, $(f(u),f(v))
%% \in E_T$.
%% In Subsection~\ref{framework}, 
Under a labeling scheme we devise for the path-tree wherein each
vertex is labeled with a 3-tuple, we can answer reachability queries
in $O(1)$ time for the path tree.  We also show that a good path-tree cover can be
extracted from $G$ to help
reduce the size of $G$'s transitive closure. %% We show that path-tree
%% can be efficiently labeled with a 3-tuple, which enables us to

Below, Section~\ref{sec:n} defines notations used in this paper.
Section~\ref{step1} describes how to partition a DAG into paths, based
on which we define the {\em path-pair subgraph} of $G$ and reveal a
nice structure of such a subgraph (Section~\ref{step2}).  We then
discuss how to extract a good {\em path-tree cover} from $G$
(Section~\ref{step3}).  We present the labeling schema for the
path-tree cover in Section~\ref{step4}.  Finally, we show how the
path-tree can be applied to compress the transitive closure of $G$ in
Section~\ref{step5}.

\subsection{Notations}
\label{sec:n}

Let $G=(V,E)$ be a directed acyclic graph (DAG), where
$V=\{1,2,\cdots,n\}$ is the vertex set, and $E \subseteq V\times V$ is
the edge set.  We use $(v,w)$ to denote the edge from vertex $v$ to
vertex $w$, and we use $(v_0,v_1,\cdots,v_p)$ to denote a {\em path}
from vertex $v_0$ to vertex $v_p$, where $(v_i,v_{i+1})$ is an edge
($0\leq i \leq p-1$).  Because $G$ is acyclic, all vertexes in a path
must be pairwise distinct.
%% A cycle is a path $(v_0,v_1,\cdots,v_p)$ with $v_0=v_s$ and
%% $(v_0,\cdots,v_{p-1})$ is a simple path.
%% Figure~\ref{figure:pathdecomp}(a) shows a DAG $G$.  
We say vertex $v$ is reachable from vertex $u$ (denoted as
$u\rightarrow v$) if there is a path starting from $u$ and ending at
$v$.

For a vertex $v$, we refer to all edges that start from $v$ as {\em
  outgoing edges} of $v$, and all edges end at $v$ as {\em incoming
  edges} of $v$.  The {\em predecessor set} of vertex $v$, denoted as
$S(v)$, is the set of all vertices that can reach $v$, and the {\em
  successor set} of vertex $v$, denoted as $R(v)$, is the set of all
vertices $v$ can reach.  The successor set of $v$ is also called 
the {\em transitive closure} of $v$.  The transitive closure of DAG
$G$ is the directed graph where there is a direct edge from each
vertex $v$ to any vertex in its successor set.
 
In addition, we say $G_s=(V_s,E_s)$ is a {\em subgraph} of $G=(V,E)$
if $V_s \subseteq V$ and $E_s \subseteq E\cap (V_s \times V_s)$.  We
denote $G_s$ as a {\em spanning subgraph} of $G$ if it covers all the
vertices of $G$, i.e., $V_s=V$.  A {\em tree} $T$ is a special DAG
where each vertex has only one incoming edge (except for the root
vertex, which does not have any incoming edge).  A {\em forest} (or
{\em branching}) is a union of multiple trees.  A forest can be
converted into a tree by simply adding a virtual vertex with an edge
to the roots of each individual tree.  To simplify our discussion, we
will use trees to refer to both trees and forest.

In this paper, we introduce a novel graph structure called {\em
  path-tree cover}.  A path-tree cover for $G$, denoted as
$G[T]=(V,E^\prime,T)$, is a spanning subgraph of $G$ and has a
tree-like shape which is described by tree $T=(V_T,E_T)$: Each vertex
$v$ of $G$ is uniquely mapped to a single vertex in $T$, denoted as
$f(v) \in V_T$ and each edge $(u,v)$ in $E^\prime$ is uniquely mapped
to a single edge in $T$, $(f(u),f(v)) \in E_T$.  %% In
%% Subsection~\ref{framework}, we show that path-tree can be efficiently
%% labeled with a three dimensional vector address and such a labeling
%% can answer reachability query with constant cost over the path-tree.
%% We show a good path-tree cover can be extract from DAG $G$ to help
%% compress the size of transitive closure of DAG $G$.


\subsection{Path-Decomposition of DAG}
\label{step1}

Let $P_1$, $P_2$ be two paths of $G$. We use $P_1 \cap P_2$ to denote
the set of vertices that appear in both of the paths, and we use $P_1
\cup P_2$ to denote the set of vertices that appear in at least one of
the two paths. We define graph partitions based on the above
terminology.

\bdefin
\label{def:pathdecomp}
Let $G=(V,E)$ be a DAG. We say a partition $P_1,\cdots, P_k$ of V is a
path-decomposition of $G$ if and only if $P_1 \cup \cdots \cup P_k=V$,
and $P_i \cap P_j = \emptyset$ for any $i\neq j$. %% ; and 2) each $P_i,
%% 1\leq i \leq k$ is a path of $G$.  
We also refer to $k$ as the width of the decomposition.  \edefin

As an example, Figure~\ref{figure:pathdecomp}(b) represents a
partition of graph $G$ in Figure~\ref{figure:pathdecomp}(a). The path
decomposition contains four paths $P_1=\{1,3,6,13,14,15\}$,
$P_2=\{2,4,7,10,11\}$, $P_3=\{5,8\}$ and $P_4=\{9,12\}$.

A simple path-decomposition algorithm is given by~\cite{Simon88}.  It can be
described briefly as follows: first, we perform a topological sort of
the DAG.  Then, we extract paths from the DAG as follows.  We find
$v$, the smallest vertex (in the ascending order of the topological
sort) in the graph and add it to the path.  We then find $v'$, such
that $v'$ is the smallest vertex in the graph that and there is an
edge from $v$ to $v'$. In other words, we repeatedly add the smallest
nodes to the latest extracted vertex until the path could not be
extended (the vertex added last has no out-going edges).  Then, we
remove the entire path (including the edges connecting to it) from the
DAG and extract another path.  The decomposition is complete when the
DAG is empty.

\begin{figure}
\centering
\begin{tabular}{cc}
\psfig{figure=Figures/DAG.epsi,width=1.6in,height=1.6in}&
\psfig{figure=Figures/PathDecomp.epsi,width=1.6in,height=1.6in}
\\
(a) & (b) \\
\end {tabular}
\caption {Path-Decomposition for a DAG}
\label{figure:pathdecomp}
\end{figure}

Based on the partition, we can identify each vertex $v$ by a pair of
IDs: (pid, sid), where pid is the ID of the path vertex $v$ belongs
to, and sid is $v$'s relative order on that path.  For instance,
vertex 3 in $G$ shown in Figure~\ref{figure:pathdecomp}(b) is
identified by (1, 2) .  For two vertices $u$ and $v$ in path $P_i$, we
use $u \preceq v$ to denote $u$ precedes $v$ (or $u=v$) in path $P_i$:
\[u \preceq v \Longleftrightarrow u.sid \leq v.sid\mbox{ and }u,v \in P_i \]

\subsection{Path Subgraph and Minimal Equivalent Edge Set}
\label{step2}

Let us consider the relationships between two paths.  We use
$P_i\rightarrow P_j$ to denote the subgraph of $G$ consisting of i)
path $P_i$, ii) path $P_j$, and iii) $E_{P_i\rightarrow P_j}$, which
is the set of edges from vertices on path $P_i$ to vertices on path
$P_j$.  For instance, $E_{P_1 \rightarrow
  P_2}=\{(1,4),(1,7),(3,4),(3,7), (13,11)\}$ is the set of edges from
vertices in $P_1$ to vertices in $P_2$.  We say subgraph $P_i
\rightarrow P_j$ is {\em connected} if
$E_{P_i\rightarrow P_j}$ is not empty.  %% We only consider the connected
%% path-pair subgraph.  

Given a vertex $u$ in path $P_i$, we want to find all vertices in path
$P_j$ that are reachable from $u$ (through paths in subgraph $P_i
\rightarrow P_j$ only). It turns out that we only need to know one
vertex -- %%  reachable from $u$, which is
the smallest (with regard to sequence id) vertex on path $P_j$
reachable from $u$. We denote its sid as $R_j(u)$.
%%   Note that for vertex $u$ in path $P_i$, we only need to
%% record at most one vertex in path $P_j$ in order to answer the
%% reachability query (here, we consider only for the reachability is
%% only for $P_i \rightarrow P_j$):
\[R_j(u)=min \{v.sid |u\rightarrow v\mbox{ and }v.pid=j\} \]
Clearly, for any vertex $v^\prime \in P_j$,
\[u\rightarrow v^\prime \Longleftrightarrow v'.sid \geq R_j(u) 
\Longleftrightarrow  u \rightarrow v\]

Certain edges in $E_{P_i \rightarrow P_j}$ can be removed without
changing the reachability between any two vertices in subgraph $P_i
\rightarrow P_j$. %%  (But, removing any edge on path $P_i$ or $P_j$ will
%% change the reachability in subgraph $P_i\rightarrow P_j$ because the
%% subgraph will become disconnected.) 
This is characterized by the following definition.

\bdefin A set of edges $E^R_{P_i\rightarrow P_j} \subseteq E_{P_i
  \rightarrow P_j}$ is called the {\em minimal equivalent edge set} of
$E_{P_i \rightarrow P_j}$ if removing any edge from
$E^R_{P_i\rightarrow P_j}$ changes the reachability of vertices in
$P_i\rightarrow P_j$.  \edefin

As shown in Figure~\ref{figure:pathpair}(a), $\{(3,4),(13,11)\}$ is
the minimal equivalent edge set for subgraph $P_1\rightarrow P_2$.  In
Figure~\ref{figure:pathpair}(b), $\{(7,6),(10,13),(11,14)\}$ is the
minimal equivalent edge set of $E_{P_2\rightarrow P_1}$=$\{(4,6)$,
$(7,6)$, $(7,14)$, $(10,13)$, $(10,14)$, $(11,14)$, $(11,15)\}$.  In
Figure~\ref{figure:pathpair}, edges belong to the minimal equivalent
edge set for subgraphs $P_i \rightarrow P_j$ in $G$ are marked in bold.

In the following, we introduce a property of the minimal equivalent
edge set that is important to our reachability algorithm.

Let $(u,v)$ and $(w,z)$ be two edges in $E_{P_i\rightarrow P_j}$,
where $u,w \in P_i$ and $v,z \in P_j$. We say the two edges are {\em
  crossing} if $u \preceq w$ (i.e., $u.sid \leq w.sid$) and $v \succeq
z$ (i.e., $v.sid \leq z.sid$).  For instance, $(1,7)$ and $(3,4)$ are
crossing in $E_{P_i,P_j}$.  Given a set of edges, if no two edges in
the set are crossing, then we say they are {\em parallel}.

\blemma No two edges in any minimal equivalent edge set of
$E_{P_i,P_j}$ are crossing, or equivalently, edges in
$E^R_{P_i\rightarrow P_j}$ are parallel.  \elemma \bproof This can
easily be proved by contradiction.  Suppose $(u,v)$ and $(w,z)$ are
crossing in $E^R_{P_i\rightarrow P_j}$. Without loss of generality,
let us assume $u \preceq w (u \rightarrow w)$ and $v \succeq z (v \leftarrow z)$. 
Thus, we have $u \rightarrow w \rightarrow z \rightarrow v$. 
Therefore $(u,v)$ is simply a short cut of $u \rightarrow v$, and dropping
$(u,v)$ will not affect the reachability for $P_i \rightarrow P_j$ as it can still be inferred through edge $(w,z)$.
\eproof

%THE ABOVE PROOF IS NOT CLEAR YET.


\blemma The minimal equivalent edge set of $E_{P_i\rightarrow P_j}$ is
unique for subbgraph $P_i\rightarrow P_j$.  \elemma

After extra edges in $E_{P_i \rightarrow P_j}$ are removed, the
subgraph $P_i \rightarrow P_j$ becomes a simple grid-like planar graph
where each node has at most $2$ outgoing edges and at most $2$
incoming edges.  This nice structure, as we will show later, allows us
to map its vertices to a two-dimensional space and enables answering
reachability queries in constant time.

\begin{figure}
\centering
\begin{tabular}{cc}
\psfig{figure=Figures/TwoPath.epsi,width=1.6in,height=1.6in}&
\psfig{figure=Figures/PathPair.epsi,width=1.6in,height=2.0in}
\end {tabular}
\caption {Path-Relationship of a DAG}
\label{figure:pathpair}
\end{figure}

A simple algorithm that extracts the minimal equivalent edge set of
$E_{P_i \rightarrow P_j}$ is sketched in
Algorithm~\ref{alg:minimalEES}.  We order all the edges from $P_i$ to
$P_j$ ($E_{P_i,P_j}$) by their end vertex in $P_2$.  Let $v^\prime$ be
the first vertex in $P_j$ which is reachable from $P_i$.  Let
$u^\prime$ be the last vertex in $P_i$ can reach $v^\prime$.  Then, we
add $(u^\prime,v^\prime)$ into $E^R_{P_i,P_j}$ and remove all the
edges in $E_{P_i,P_j}$ which start from a vertex in $P_i$ which
proceed $u^\prime$ (or cross edge $(u^\prime, v^\prime)$.  We repeat
this procedure until the edge set $E^R_{P_i,P_j}$ becomes empty.

\input{Figures/MinimalEES}


\subsection{Path-Graph and its Spanning Tree (Path-Tree)}
\label{step3}
We create a directed {\it path graph} for DAG $G$ as follows. Each
vertex $i$ in the path graph correponds to a path $P_i$
in $G$. %% is
%% represented as a vertex $i$ and 
If path $P_i$ connects to $P_j$ in $G$, we create an edge $(i,j)$ in
the path graph.  %% We refer to this graph as a
%% {\em path-graph}.
Let $T$ be a directed spanning tree (or a forest) of the path-graph.
Let $G[T]$ be the subgraph of $G$ that contains i) all the paths of
$G$, and ii) the minimal edge sets, $E^R_{P_i\rightarrow P_j}$, for
every $i$, $j$ if edge $(i,j) \in T$.  We will show that there is a
vector labeling for $G[T]$ which can answer the reachability query for
$G[T]$ in constant time.  We refer to $G[T]$ as the {\em path-tree
  cover} for DAG $G$.

Just like Agrawal {\em et. al}'s tree cover~\cite{SIGMOD:AgrawalBJ:1989}, in order to
utilize the path-tree cover, we need to ``remember'' those edges that
are not covered by the path-tree.  Ideally, we would like to minimize
the index size, which means we need to minimize the number of the
non-covered edges.  Meanwhile, unlike the tree cover, we want to avoid
computing the transitive closure (computing the predecessor set of
each vertex is equivalent to computing the transitive closure).  In
the next subsection, we will investigate how to find the optimal
path-tree cover if such knowledge is available.
%Essentially, without partially computing the transitive closure, we will not be able to compute the cost of the index.
Here, we introduce a couple of alternative criteria which can help
reduce the index size without such knowledge.

\begin{figure}
  \centering
\begin{tabular}{cc}
\psfig{figure=Figures/PathDirectedGraph.epsi,width=1.6in,height=1.2in}&
\psfig{figure=Figures/PathTree.epsi,width=1.6in,height=1.2in}
\\
(a) & (b) \\
\end {tabular}
\caption {(a) Weighted Path Directed Graph \& (b) Maximal Directed Spanning Tree}
\label{figure:pathdirectedgraph-tree}
\end{figure}

The first criterion is referred to as {\em MaxEdgeCover}.  The main
idea is to use the path-tree to cover as many edges in DAG $G$ as
possible.  Let $t$ be the remaining edges in DAG $G$ (edges not
covered by the path-tree).  As we will show later in this subsection,
$t$ provides an upper-bound for the compression of transitive closure
for $G$, i.e., each vertex needs to record at most $t$ vertices for
answering reachability query.  Given this, we can simply assign
$|E_{P_i \rightarrow P_j}|$ as the cost for edge $(i,j)$ in the
directed tree-graph.

The second criteria, referred to as {\em MinPathIndex}, is more
involved.  As we discussed in the path-decomposition, each vertex
needs to remember at most one vertex on any other path to answer the
reachability query.  Given two paths $P_i$, $P_j$, and their link set
$E_{P_i\rightarrow P_j}$, we can quickly compute the index cost as
follows if $E_{P_i \rightarrow P_j}$ does not include the tree-cover.
%We assign the cost from path $P_i$ to path $P_j$ as follows. 
Let $u$ be the last vertex in path $P_i$ that can reach path $P_j$.
Let $P_i[\rightarrow u]=\{v| v \in P_i, v \preceq u\}$ be the
subsequence of $P_i$ that ends with vertex $u$.  For instance, in our
running example, vertex $13$ is the last vertex in path $P_1$ which
can reach path $P_2$, and $P_1[\rightarrow 13]=\{1,3,6,13\}$
(Figure~\ref{figure:pathpair}).  We assign a weight $w_{P_i,P_j}$ to
be the size of the $P_j[\rightarrow u]$.  In our example, the weight
$w_{P_1,P_2}=4$.  Basically, this weight is the labeling cost if we
have to materialize the reachability information for path $P_i$ about
path $P_j$.  Considering path $P_1$ and $P_2$, we only need to record
vertex $4$ in path $P_2$ for vertices $1$ and $3$ in path $P_1$ and
vertex $11$ for vertices $6$ and $13$.  Then, we can answer if any
vertex in $P_2$ can be reached from any vertex in $P_1$.  Thus,
finding the maximum spanning tree in such a weighted directed
path-graph corresponds to minimizing the index size by using path
labeling schema.  Figure~\ref{figure:pathdirectedgraph-tree}(a) is the
weighted directed path-graph using the {\em MinPathIndex} criteria.

To reduce the index size for the path-tree cover, we would like to
extract the maximum directed spanning tree (or forest).
Chu-Liu/Edmonds algorithm can be directly applied to this
problem~\cite{ChuLiu65,Edmonds67}. The fast implementation that uses
the Fibonacci heap requires $O(m^\prime+klogk)$ time complexity, where
$k$ is the width of path-decomposition and $m^\prime$ is the number of
directed edges in the directed path-graph~\cite{Gabow86}.  Clearly, $k \leq n$ and 
$m^\prime \leq m$, $m$ is the number edges in the original DAG.

\subsection{Reachability Labeling for Path-Tree}
\label{step4}
In this section, we introduce a vector labeling scheme for vertices in
the path-tree. The labeling scheme enables us to answer reachability
queries in constant-time.  We partition the path-tree into paths, and
we call the result a path-path cover, and denote it as $G[P]$.

We start with a simple scenario. 
%%  derive a new cover denote : the paths in the path-decomposition form
%% a path in the path-tree, which we refer to as the {\em path-path}
%% cover and denote as $G[P]$.  
For example, in Figure~\ref{figure:simplelabel}, we have the
path-path: $(P4,P2,P1)$.  We map each vertex in the path-path to a
two-dimensional space as follows.  First, all the vertices in each
single path have the same path ID, which we define to be $Y$.  For
instance, vertices $P4, P2$ and $P1$ have order $1,2,$ and $3$,
respectively.

\input{Figures/DFSLabel.tex} 

Then, we perform a depth-first search (DFS) to assign the $X$ label
for each vertex (The procedure sketch is in
Algorithm~\ref{alg:DFSLabel}).  For labeling purposes, in the linked
list for each vertex, we always put its neighbor on the same path (the
right neighbor, if it exists) ahead of its neighbors on other paths
(the upper neighbor, if it exists).  This basically allows us to visit
the vertices in the same path before any other vertices.  In the DFS
search, we will maintain a counter $N$ which records the number of all
vertices in the graph initially (In our running example, $N=13$, see
Figure~\ref{figure:simplelabel}).  To start the DFS search, we begin
with the first vertex $v_0$ in the first path.  In our example, it is
the vertex $9$ in path $P4$.  Starting from this vertex, our DFS
always tries to visit its right neighbor and then tries to visit its
upper neighbor.  For a given vertex, when we finish visiting all of
its neighbors, we assign this vertex the label $N$ and reduce $N$ by
$one$.  Once we visit all the vertices which can be reached from
$v_0$, we start from the first vertex in the second path if it has not
been visited.  We continue this process until all the vertices have
been visited.  Note that our labeling procedure bears some similarity
to ~\cite{kameda75}.  However, their procedure can handle only a
specific type of planar graph, whereas our labeling procedure will
handle path-tree procedure which can be a non-planar graph.


Figure~\ref{figure:simplelabel}(a) shows the the $X$ label based on the DFS procedure. 
Figure~\ref{figure:simplelabel}(b) shows the embedding of the path-path in the two dimensional space based on their $X$ and $Y$ labels. 

\blemma
\label{pathpathlabel}
Given two vertices $u$ and $v$ in the path-path, $u$ can reach $v$ if
and only if $u.X \leq v.X$ and $u.Y \leq v.Y$ (this is also referred
to as $u$ dominates $v$).  \elemma

\bproof \ First, we prove $u \rightarrow v \Longrightarrow u.X \leq
v.X \wedge u.Y \leq v.Y$.  Clearly if $u$ can reach $v$, then $u.Y
\geq v.Y$ (path-path property), and DFS traversal will visit $u$
earlier than $v$, and only after visiting all $v$'s neighbor will it
return to $u$.  So, $X(v) > Y(v)$ based on DFS.  Second, we prove $u.X
\leq v.X \wedge u.Y \leq v.Y \Longrightarrow u \rightarrow v$.  This
can be proved by way of contradiction.  Let us assume $u$ can not
reach $v$.  Then, (Case 1:) if $u$ and $v$ are on the same path
($u.Y=v.Y$), then $u.sid>v.sid$, i.e., we will visit $v$ before we
visit $u$. In other words, we complete $u$'s visit before we complete
$v$'s visit. Thus, $u.X>v.X$, which contradicts our assumption.  (Case
2:) if $u$ and $v$ are on different paths ($u.X < v.X$), similar to
case 1, we will complete the visit of $u$ before we complete the visit
of $v$ as $u$ can not reach $v$. So, $u.X>v.X$.  Combining both cases
$1$ and $2$, we prove our result.  \eproof

For the general case, the paths form a tree instead of a single path.
In this case, each vertex will have an additional interval labeling
based on the tree structure.  Figure~\ref{figure:completelabel}(c)
shows the interval label of the path-tree in
Figure~\ref{figure:completelabel}(a).  All the vertices on the path
share the same interval label for this path.  Besides, the $Y$ label
for each vertex is generalized to be the level of its corresponding
path in the tree path, i.e., the distance from the path to the root
(we assume there is a virtual root connecting all the roots of each
tree in the branching/forest).  The $X$ label is similar to the simple
path-path labeling.  The only difference is that each vertex can have
more than one upper-neighbor.  Besides, we note that we will traverse
the first vertex in each path based on the path's level in the
path-tree and any of the traversal orders of the paths in the same
level will work for the $Y$ labeling.
Figure~\ref{figure:completelabel}(a) shows the $X$ label of all the
vertices in the path-tree and Figure~\ref{figure:completelabel}(b)
shows the two dimensional embedding.

\blemma
\label{pathtreelabel}
Given two vertices $u$ and $v$ in the path-tree, $u$ can reach $v$ if
and only if 1) $u$ dominates $v$, i.e., $u.X \leq v.X$ and $u.Y \leq
v.Y$; and 2) $v.P \subseteq u.P$, where $u.P$ and $v.P$ are the
interval labels of $u$ and $v$'s corresponding paths.  \elemma 
\bproof
First, we note that the procedure will maintain this fact that if $u$
can reach $v$, then $u.X \leq v.X$. This is based on the DFS
procedure.  Assuming $u$ can reach $v$, then, there is a path in the
tree from $u$'s path to $v$'s path. So we have $v.P \subseteq u.P$
(based on the tree labeling) and $u.Y \leq v.Y$.  In addition, we have
$v.P \leq u.P$, then, there is a path from $u$'s path from $v$'s path.
Then, using the similar argument from Lemma~\ref{pathpathlabel} shows
that if $u.X \leq v.X$ then $u$ can reach $v$.  \eproof

\bthm The three dimensional vector labeling is sufficient for
answering the reachability query for any path-tree.  \ethm \bproof
Note that if $v.P \subseteq u.P$, then $v.Y \geq u.Y$. Thus, we can
drop $Y$'s label without losing any information.  Thus, for any vertex
$v$, we have $v.X$ (the first dimension) and $v.P$ (the interval for
the last two dimensions).  \eproof
  
\begin{figure}
\centering
\begin{tabular}{c}
\psfig{figure=Figures/PathTreeLabeling.epsi,width=3.0in,height=3.0in}
\end {tabular}
\caption {Labeling for Simple Path-Tree}
\label{figure:simplelabel}
\end{figure}

\begin{figure}
\centering
\begin{tabular}{c}
\psfig{figure=Figures/CompletePathTreeLabeling.epsi,width=3.0in,height=3.0in}
\end {tabular}
\caption {Complete Labeling for the Path-Tree}
\label{figure:completelabel}
\end{figure}

The overall construction time of the path-tree cover is as follows.
The first step of path-decomposition is $O(n+m)$, which includes the
cost of the topological sort.  The second step of building the
directed path graph is $O(m)$.  The third step of extracting the
maximum spanning tree is $O(m^\prime+klogk)$, where $m^\prime \leq m$
and $k \leq n$.  The fourth step of labeling basically utilizes a DFS
proceduce which costs $O(m^{\prime\prime}+n)$, where
$m^{\prime\prime}$ is the number of edges in the path-tree and
$m^{\prime\prime} \leq m$.  Thus, the total construction time of
path-tree cover is $O(m+nlog n)$.

\subsection{Transitive Closure Compression and Reachability Query Answering}
\label{step5}
Edges not included in the path-tree cover can result in extra
reachability which will not be covered by the path-tree structure.  To
answer the reachability query for the entire DAG, the simplest
strategy is to actually construct the transitive closure for the DAG.
However, the path-tree structure will help us significantly reduce the
transitive size (index size) and its construction time as well.  Let
$R^c(u)$ be the compressed set of vertices we record for the
transitive closure utilizing the the path tree.  Let $u$ be a vertex
in $P_i$.  For any two vertices $x$ and $y$ in $R^c(u)$, if $y$ is
reachable from $x$ based on the path-tree, then $y$ will not be
included in the $R^c(u)$.  Thus, to answer a reachability query for
$u$ and $v$ (i.e. if $v$ is reachable from $u$), we need to test 1) if
$v$ is reachable from $u$ based on the path-tree labeling and if not
2) for each $x$ in $R^c(u)$, whether $v$ is reachable from $x$ based on the
path-tree labeling.  We note that $R^c(u)$ includes at most one vertex
from any path and in the worst case, $|R^c(u)|=O(k)$, where $k$ is number
of paths in the path-tree.
Thus, a query would cost $O(k)$. In Subsection~\ref{intervalquery}, 
we will introduce a procedure which costs $O(log ^2k)$. 

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "paper"
%%% End: 
